package q1109_corpFlightBookings;

public class Solution {

    /*
    差分数组对应的概念是前缀和数组，对于数组 [1,2,2,4]，其差分数组为 [1,1,0,2]，
    差分数组的第 i 个数即为原数组的第 i−1 个元素和第 i 个元素的差值，
    也就是说我们对差分数组求前缀和即可得到原数组。
     */
    public int[] corpFlightBookings(int[][] bookings, int n) {
        int[] nums = new int[n];
        for (int[] booking : bookings) {
            /*
            为了仅仅让原数组下标在[l,r]区间内的元素值增加 inc
            首先需要将差分数组d[l]位置加 inc,这样下标 >= l 位置的元素都获得inc增量
            其次,为了不影响原数组中下标大于 r 的元素,需要在d[r + 1]处减去inc,使得原数组下标 > r 的元素值不变.
             */
            nums[booking[0] - 1] += booking[2];
            if (booking[1] < n) nums[booking[1]] -= booking[2];
        }

        for (int i = 1; i < n; i++) nums[i] += nums[i - 1];

        return nums;
    }

    /*
    最直观的做法 但是超时
     */
    public int[] WorseCorpFlightBookings(int[][] bookings, int n) {
        int[] ans = new int[n];
        for (int i = 0; i < ans.length; i++) {
            for (int j = 0; j < bookings.length; j++) {
                if (i >= bookings[j][0] && i <= bookings[j][1]) ans[i] += bookings[j][2];
            }
        }
        return ans;
    }



}
